// 跳表
const P = 1 / Math.E

class Node {
  constructor(level, key, value) {
    this.node = new Array(4 + level)
    this.node[0] = key
    this.node[1] = value
  }
}

class SkipList {
  
  constructor(maxLevel, maxsize, listLevel) {
    this.dataStore = []
    
    this.maxLevel = maxLevel || 7
    this.maxsize = maxsize || 777
    this.listLevel = listLevel
    
    this.head = new Node(this.maxLevel).node
    this.tail = new Node(-1).node
    
    for(let i = 0; i < this.maxLevel; i++) {
      this.head[i + 3] = this.tail
    }
    
    this._update = new Array(this.maxLevel + 1)

    for(let i = 0; i < this._update.length; i++) {
      this._update[i] = this.head;
    }

  }

  nodesEqual(left, right) {
    if ((left === undefined) && right) return false
		if ((right === undefined) && left) return false
		if (left[0] !== right[0]) return false
		if (left[1] !== right[1]) return false
		if (left[2] !== right[2]) return false
		if (left[3] !== right[3]) return false
		
		return true
  
	}

  find(search, reverse) {
 		const node = reverse ? this.tail : this.head[3];
		const idx = reverse ? 2 : 3;
		const results = [];

		if (search) {
			const update = this._update.slice(0);
			const found = this._findLess(update, search)
			if (!this.nodesEqual(found[3], new Node(-1).node))
				node = found[3]
		}

		while (node[0]) {
			results.push([node[0], node[1]])
			node = node[idx]
		}

		return results
  }

	_findLess(update, search) {
		var node = this.head
		for (var i = this.level; i >= 0; i--) {
			var key = node[3 + i][0]
			
			while (key && (key < search)) {
				node = node[3 + i];
				key = node[3 + i] ? node[3 + i][0] : null
			}
		
			update[i] = node
		}

		return node
	}
  
  insert(key, value) {
    let update = this._update.slice(0)
    let node = this._findLess(update, key)
    let prev = node
    
    if(node[0] === key) {
      node[1] = value     
    } else {
      
      const lvl = this._randomLevel()
      this.level = Math.max(this.level, lvl)
      
      node = new Node(lvl, key, value).node
      node[2] = prev
      
      for (var i = 0; i <= this.level; i++) {
        node[3 + i] = update[i][3 + i]
        update[i][3 + i] = node
      }

      if(this.nodesEqual(node[3], new Node(-1).node)) {
        this.tail = node
      } else {
        node[3][2] = node
      }
    }
  }
  
  _randomLevel() {
    let lvl = 0
    const max = Math.min(this.maxlevel, this.level + 1)
    while ((Math.random() < P) && (lvl < max)){
      lvl++  
    }

    return lvl
  }	

}

const skipList = new SkipList(122)
skipList.insert("qiqi", 77)
console.log(skipList.find(0))
